/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-12-02
 * Time: 22:48
 */
public class Solution {
    //dp
    // public int minPathSum(int[][] grid) {
    //     int row=grid.length;
    //     int col=grid[0].length;
    //     int[][] dp=new int[row][col];
    //     //先将第一个元素添加进去
    //     dp[0][0]=grid[0][0];
    //     //将第一行元素设置好(因为第一行元素只依赖于左边的元素,所以可以直接确定)
    //     for(int i=1;i<col;i++){
    //         dp[0][i]=grid[0][i]+dp[0][i-1];
    //     }
    //     //将第一列元素设置好(因为第一列元素只依赖于上边的元素,所以可以直接确定)
    //     for(int i=1;i<row;i++){
    //         dp[i][0]=grid[i][0]+dp[i-1][0];
    //     }
    //     //某位置的元素的最小值,依赖于左边和上边中较小值+该位置元素
    //     for(int i=1;i<row;i++){
    //         for(int j=1;j<col;j++){
    //             dp[i][j]=grid[i][j]+Math.min(dp[i][j-1],dp[i-1][j]);
    //         }
    //     }
    //     return dp[row-1][col-1];
    // }

    //dp空间优化,二维数组优化为一维即滚动数组
    public int minPathSum(int[][] grid) {
        int row=grid.length;
        int col=grid[0].length;
        int[] dp=new int[col];
        dp[0]=grid[0][0];
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                //第一行
                if(i==0&&j>0){
                    dp[j]=dp[j-1]+grid[i][j];
                }else if(j==0&&i>0){
                    //第一列
                    dp[j]+=grid[i][j];
                }else if(i>0&&j>0){
                    //不要忘记if语句里面的判断,否则-1
                    //其他位置的元素
                    //dp数组中的元素代表的位置从前往后挨个往下调一行
                    dp[j]=grid[i][j]+Math.min(dp[j-1],dp[j]);
                }
            }
        }
        return dp[col-1];
    }
}
